\documentclass{beamer}
\usepackage{ctex}
\usetheme{Madrid}

\author{uncle-lu}
\institute{乌鲁木齐市第一中学}
\title{NOIP2016Day2 解析报告}
\date{\today}

\begin{document}

    \frame{\titlepage}

    \section{概述}

    \begin{frame}\frametitle{概述}
        \begin{itemize}
            \item 第一题  组合数问题
            \item 第二题  蚯蚓
            \item 第三题  愤怒的小鸟
        \end{itemize}

        总的来说:相对于Day1.个人觉得还是比较可做.

        这是件很可怕的事情.

        \pause

        告诉我们及时调整心态的重要性.
    \end{frame}

    \section{第一题}

    \begin{frame}\frametitle{第一题}
        \textbf{题目概述:}

        给定 $n,m,k$ 求出对于所有的 $ 0 \leq i \leq n , 0 \leq j \leq min(i,m) $ 中 有多少对 $(i,j)$ 满足 $C_i^j$ 是k的倍数.

        \pause 

        对于拿到题目的瞬间.这个是一道裸数学题???

    \end{frame}

    \begin{frame}\frametitle{分析}
        拿到题我们应该对于整个题面读完整.包括数据范围.

        我们发现这道题还是有些可写的地方(如果你不会组合数)

        接下来我们就分析一下各个算法.
    \end{frame}

    \begin{frame}\frametitle{算法一}
        当我们不会组合数的时候.怎么办!!

        \pause

        最笨的方法就是按照题目的想发来一步一步的算.

        \pause

        所以算法一.

        先预处理所有的阶乘.

        然后按照题目的要求来处理.

        时间复杂度$O (t*n^2)$ 其实就是$O(n^3)$的算法

        \pause

        但是我们发现其实有些阶乘存不下?我们可以边模边乘?

        \pause 

        答案是不行.

        组合数中有除法.我们没有类似的运算率可以这样搞.

        所以?

        \pause

        算法一预计得分40.

        \pause

        其实你也可以不预处理阶乘.这样分更少.

    \end{frame}

    \begin{frame}\frametitle{算法二}
        突然我们就会了组合数.

        \pause

        对于这道题我们可以引用一个非常厉害的东西.

        \pause

        杨辉三角.

        \pause

        其实就是
        
        \[C(n+1,i)=C(n,i)+C(n,i-1)\]

        有了这个递推式我们就可以预处理出整个组合数.

        \pause

        之后我们在按照题目要求 用 $O(t*n^2)$ 的方法来处理.

        这个方法应该会A吧.

        \pause

        算法二预计得分90.

    \end{frame}

    \begin{frame}\frametitle{算法三}
        对于一般的dalao来说.写出算法二的复杂度就很轻松发现这个复杂度会炸.

        \pause

        所以我们需要对它进行优化.

        \pause

        其实这也是一般考试的时候一个小技巧.

        先写暴力.然后优化优化优化.之后万一优化成正解呢?.

        不存在的.

        \pause

        算法三使用前缀和优化.对于每行\(C_i\)我们可以用前缀和来处理.

        \pause

        那么我们查询的时候就会少遍历一个$n$

        算法复杂度为$O(t*n)$

        \pause
        
        算法三预计得分100.
    \end{frame}

    \begin{frame}\frametitle{算法四}
        其实算法三就够了.但是我们还是讲一下算法四.

        \pause

        我们算法三使用前缀和优化一整列.

        其实我们可以用前缀和来优化整个矩阵.

        \pause

        这样我们查询就可以又少遍历一个$n$

        算法复杂度就会变成$O(t)$

        \pause

        算法四预计得分100.
    \end{frame}

    \section{第二题}

    \begin{frame}\frametitle{第二题}
        \textbf{题目概述:}

        有一个序列.每一秒对序列中的最大值进行拆分.其他没有拆分的数.还要增大.

        之后还要根据题目要求进行动态输出.

        \pause

        看起来很难.

        不知道怎么下手.

    \end{frame}

    \begin{frame}\frametitle{分析}
        一般对序列进行维护的题.数据结构.

        \pause

        嗯.直觉.

        \pause

        有很多数据结构可以刚过这道题.

        这里就介绍一种.
    \end{frame}

    \begin{frame}\frametitle{算法一}
        通过观察我们这里有很多$q=0$的点.

        \pause

        所以我们可以不用考虑增长的问题.

        直接根据题意套用优先队列.

        硬肛.

        \pause

        算法复杂度 O(不正确)

        算法一预计得分:50分.
    \end{frame}

    \begin{frame}\frametitle{算法二}
        因为算法一中没有考虑增长问题.

        \pause

        于是我们可以想到可以手写堆来暴力增长.

        \pause

        算法复杂度$O((n+m)^2 nlogn)$


        算法二预计得分:35分.
    \end{frame}

    \begin{frame}\frametitle{算法三}
        我们发现算法二在处理增长的时候会遍历整个堆.

        $q=0$的点复杂度就浪费了.

        \pause

        所以算法三就为算法一+算法二.

        加个特判.

        \pause

        算法复杂度O(不正确+玄学)

        算法三预计得分:60分.
    \end{frame}

    \begin{frame}\frametitle{算法四}
        什么是真正的技术？

        \pause

        真正的技术是.

        \begin{center}
            \textbf{摆脱现有的思维,开启新的思维.}
        \end{center}

        \pause

        因为算法三已经到了 关于用二叉堆 来维护这道题的极限.

        你找不到可以用什么来优化它.复杂度也不知道该怎么改进.

    \end{frame}

    \begin{frame}\frametitle{算法四}
        第一次对数进行拆分与第二次对数进行拆分有什么关系?

        \pause

        我们发现前面拆分出来的数一定要比之后拆分出来的数要大.

        \pause

        因为每次我们取的最大的.而后面再取的基数不可能比它还大.

        所以我们发现这个拆分出来的数具有单调性.

        \pause

        所以我们根本没必要用优先队列来动态维护这些数.

        我们可以开3个队列.

        每次取3个队列中头.

        因为头永远是该队列中的最大的(单调性).

        这样我们的取与存 就是$O(1)$的操作.
    \end{frame}

    \begin{frame}\frametitle{算法四}
        但是序列中的增长怎么处理?

        \pause

        其实我们没必要每次都去处理.

        取到该数到时候我们再对它进行增长操作.

        类似于一种懒惰操作.

        \pause

        算法四时间复杂度 $O(n+m)$

        算法四预计得分:100分.
    \end{frame}

    \section{第三题}

    \begin{frame}\frametitle{第三题?}
        \textbf{题目概述:}
         
        愤怒的小鸟.

        \pause

        第一直觉

        数学?

        n<=18

        搜索?

        这都什么东西.
    \end{frame}

    \begin{frame}\frametitle{分析}
        我也不会做啊.

        这暴力怎么写啊?!!!

        这部分分有什么可以拿的吗?

    \end{frame}

    \begin{frame}\frametitle{算法一}
        这道题我们直接来讲正解.

        \pause

        但是讲正解之前我们先处理一下一些小细节.
    \end{frame}

    \begin{frame}\frametitle{细节一}
        二次函数怎么处理啊.
        \pause

        此题的二次函数为简化的二次函数.

        \[ y=ax^2 + bx\]

        \pause

        所以此题中我们已知2点就可以推出一条抛物线.
    \end{frame}

    \begin{frame}\frametitle{抛物线推导}
    已知$(x_1,y_1) (x_2,y_2)$与\(y=ax^2 + bx\)
    
    将$(x_1,y_1) (x_2,y_2)$代入方程中可得

    \begin{displaymath}
        \left\{ \begin{array}{ll}
            y_1= a x_1^2 + b x_1 & \textcircled{1}\\
            y_2= a x_1^2 + b x_2 & \textcircled{2} 
        \end{array} \right.
    \end{displaymath}

    由\textcircled{1}可得
        \[
        y_1 = a x_1^2 + b x_1
        \]
        \[
            b = 
            \frac{ y_1-a x_1^2 }{ x_1 } 
            \qquad \textcircled{3}
        \]
    \end{frame}

    \begin{frame}\frametitle{抛物线推导}
        将\textcircled{3}代入\textcircled{2}中
        
            \[
            y_2=a x_2^2 +
            \frac{ y_1-a x_1^2 }{ x_1 }
            x_2 
            \]
            \[
            y_2=a x_2^2 +(
            \frac{ y_1 }{ x_1 }
            - a
            \frac{ x_1^1 }{ x_1 }
            ) x_2 
            \]
            \[
            y_2=a x_2^2 +
            \frac{ x_2 y_1 }{ x_1 } 
            - a x_1 x_2 
            \]
            \[
            y_2 - 
            \frac{ x_2 y_1 }{ x_1 } 
            = ( x_2^2 - x_1 x_2) a 
            \]
            \[
            a = 
            \frac{ y_2- 
            \frac{ x_2 y_1 }{ x_1 }
            }{ x_2^2 - x_1 x_2 } 
            \]
        
            于是乎我们很轻松就可以算出a与b. 
    \end{frame}

    \begin{frame}\frametitle{细节二}
        我们该怎么表示那些点用了?

        \pause

        状态压缩.

        \pause

        由于我们的n只有18

        所以我们可以使用一个二进制数来表示每一个猪被打掉的情况.

        \pause

        比如说我们有7个猪.第3\quad4\quad5\quad6被打掉了
        我们可以表示为
        \[
            (0111100)_2 = (60)_{10}
        \]
    \end{frame}

    \begin{frame}\frametitle{算法一}
        细节二里提到了状态压缩.

        所以我们的可以使用状态压缩DP.来处理这些问题.

        \pause

        \textbf{状态是什么}

        \pause

        细节二

        我们用猪是否被打掉作为状态.

        \pause

        \textbf{怎么转移状态}
        
        \pause

        对于任何一个猪.我们可以选择和其他猪一起组成一个抛物线然后打掉抛物线上相同的一些猪.

        \[
        F[i+(1<<(x-1))]=min(F[i+(1<<(x-1))],F[i]+1)
        \]
    \end{frame}

    \begin{frame}\frametitle{算法一}
        \begin{itemize}
            \item 首先我们预处理每两个猪组成的抛物线可打掉些谁.
            \item 之后我们枚举\(F[0]\)到\(F[(1<<n)-1]\).进行转移
        \end{itemize}

        \pause

        算法一时间复杂度$O(2^n * n^2)$

        \pause

        算法一预计得分:100分.
    \end{frame}

    \begin{frame}\frametitle{算法二}
        搜索.

        还是按刚才的状态表示方法.

        不过我们可以暴力枚举下一个选的猪.

        唔.如果算法一懂了.算法二就很好想了.
    \end{frame}

    \begin{frame}\frametitle{总结}
        \begin{itemize}
            \item 无论怎么说,先写个暴力保个底.
            \pause
            \item 本次NOIP的编排顺序很操蛋.所以先读完题再做.
            \pause
            \item 要合理估计算法复杂度.合理安排时间.
        \end{itemize}
    \end{frame}

    \begin{frame}\frametitle{结束}
        以上为全部内容.

        讲课人:uncle-lu

        博客:uncle-lu.org

        本次讲课资料(包括源码):https://gitee.com/uncle-lu/Tex-Doc

        Bilibili直播间:https://live.bilibili.com/1269934
    \end{frame}
\end{document}